/**
 * 在地下室里放着n种颜色的手套，手套分左右手，但是每种颜色的左右手手套个数不一定相同。
 * A先生现在要出门，所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色，只能分辨出左右手。
 * 所以他会多拿一些手套，然后选出一双颜色相同的左右手手套。现在的问题是，他至少要拿多少只手套(左手加右手)，
 * 才能保证一定能选出一双颜色相同的手套。
 *
 * 给定颜色种数n(1 ≤ n ≤ 13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。
 * 数据保证左右的手套总数均不超过26，且一定存在至少一种合法方案。
 *
 * 测试样例：
 * 4,[0,7,1,6],[1,5,0,6].
 * 返回：10 (解释：可以左手手套取2只，右手手套取8只).
 */
public class Gloves {
    /*
     * *有两种方式：
     * 1：把左手套全部拿出来，右手套选出一个，即可配对
     * 2：把右手套全部拿出来，左手套选出一个，即可配对
     * 但是这两种方法缺乏一点考虑，1中从右手套中选出配左手套，有一种情况
     * 左手套中可能有一种颜色为0，而右手套却有这种颜色，这时如果选择这个右手套
     * 就不可以配对，所以总数需要1+这类右手套的个数才可成功配对，此外还有一点
     * 需要考虑，就是只需要配对一个即成功，所以把左右手套都有的颜色中 左手套个数
     * 最少的手套数变为1，因为多了也是冗余。2中类似。
     * 程序中的max = max - min + 2可以理解为
     * max = max - (min - 1) + 1
     */

    public static int findMinimum(int n, int[] left, int[] right) {

        int max1 = 0,min1 = 27;
        int max2 = 0,min2 = 27;
        for(int i = 0;i < n; i++){
            if(left[i] == 0){
                max1 = max1 + right[i];
            } else{                     //1->8->9->15
                max1 = max1 + left[i];
            }

            if(right[i] == 0){
                max2 = max2 + left[i];
            } else{
                max2 = max2 + right[i]; //1->6->7->13
            }

            if(left[i] != 0 && right[i] != 0 && left[i] < min1){
                min1 = left[i]; // 5
            }
            if(right[i] != 0 && left[i] != 0 && right[i] < min2){
                min2 = right[i]; // 5
            }
        }
        max1 = max1 - min1 + 2;
        max2 = max2 - min2 + 2;

        return Math.min(max1, max2);
    }
    public static void main(String[] args) {
        int[] left = {0, 7, 1, 6};
        int[] right = {1, 5, 0, 6};
        System.out.println(findMinimum(4, left, right)); // 10
        System.out.println(findMinimum2(4, left, right)); // 10
    }

    /**
     *  题解
     */
    public static int findMinimum2(int n, int[] left, int[] right) {
        int leftSum = 0;
        int rightSum = 0;
        int leftMin = 27, rightMin = 27;
        int sum = 0;
        for(int i = 0; i < n; ++i) {
            if(left[i] * right[i] == 0)
                sum += left[i] + right[i];
            else {
                leftSum += left[i];
                rightSum += right[i];
            }
            if(left[i] != 0 && right[i] != 0 && left[i] < leftMin)
                leftMin = left[i];
            if(left[i] != 0 && right[i] != 0 && right[i] < rightMin)
                rightMin = right[i];
        }
        return Math.min(leftSum - leftMin + 1, rightSum - rightMin + 1) + 1 + sum;
    }
}
